package algotithm.weekendrace.leetcode283.test2;

import java.util.*;

/**
 * @author tom
 * @date 2022-03-06 10:50
 */
class Solution {
    public long minimalKSum(int[] nums, int k) {
        long res = 0;
        int n = nums.length;
        int pre = 0;
        Arrays.sort(nums);
        for (int i = 0; i < n; i++) {
            if (nums[i] - pre > k) {
                res += (long) ((pre + 1) + (pre + k)) * k / 2;
                return res;
            } else if (nums[i] - pre <= 1) {
                pre = nums[i];
            } else {
                res += (long) ((pre + 1) + (nums[i] - 1)) * (nums[i] - pre - 1) / 2;
                k -= (nums[i] - pre - 1);
                pre = nums[i];
            }

        }
        if (k > 0) {
            res += (long) (nums[n - 1] + 1 + nums[n - 1] + k) * k / 2;
        }
        return res;
    }
}
